/**
 * 将一个带头结点的单链表A分解为两个带头结点的单链表A和B，
 * 使得A表中含有原表中序号为奇数的元素，
 * B表中含有原表中序号为偶数的元素，并保持相对顺序不变
 */

#include <stdio.h>
#include <stdlib.h>

#define bool int
#define true !0
#define false 0

typedef struct LNode{
	struct LNode* next;
	int data;
} LNode, *LinkedList;

bool init(LinkedList &list);

bool insert(LinkedList &list, int data);

void print(LinkedList &list);

bool core(LinkedList &A);

int main()
{
	LinkedList list=NULL;
	init(list);
	insert(list,1);
	insert(list,3);
	insert(list,2);
	insert(list,5);
	insert(list,9);
	insert(list,12);	
	insert(list,6);
	insert(list,8);
	print(list);
	core(list);
	return 0;
}

bool init(LinkedList &list)
{
	LNode* newNode=(LNode* )malloc(sizeof(LNode));
	if(!newNode) return false;
	newNode->next=NULL;
	list=newNode;
	return true;
}

bool insert(LinkedList &list, int data)
{
	LinkedList node=list;
	while(node->next) node=node->next;
	LNode* newNode=(LNode* )malloc(sizeof(LNode));
	if(!newNode) return false;
	newNode->next=NULL;
	newNode->data=data;
	node->next=newNode;
	return true;
}

void print(LinkedList &list)
{
	LinkedList node=list->next;
	while(node)
	{
		printf("%d ",node->data);
		node=node->next;
	}
	printf("\n");
}

bool core(LinkedList &A)
{
	int index=0;
	LinkedList B=(LNode* )malloc(sizeof(LNode));
	if(!B) return false;
	B->next=NULL;
	
	LNode* pointA=A;		//pointA指针指向链表A的最后一个元素(默认指向头结点)
	LNode* pointB=B;		//pointB指针指向链表B的最后一个元素(默认指向头结点)
	LNode* node=A->next;	//A结点为遍历结点，指向A链表的第一个元素
	A->next=NULL;			//A链表中的元素"清0(置空)"
	while(node)
	{
		index++;
		if(index%2==0)
		{
			//如果是偶序号，插入到B链表中
			pointB->next=node;
			pointB=node;
		} else {
			//否则是奇序号,插入到A链表中
			pointA->next=node;
			pointA=node;
		}
		node=node->next;
	}
	pointA->next=NULL;
	pointB->next=NULL;
	
	printf("core后:\n");
	print(A);
	print(B);
	return true;
}